# -*- coding: utf-8 -*-

"""
    http://projecteuler.net/problem=28
    
    PROBLEM
    
    Starting with the number 1 and moving to the right in a clockwise
    direction a 5 by 5 spiral is formed as follows:

    21 22 23 24 25
    20  7  8  9 10
    19  6  1  2 11
    18  5  4  3 12
    17 16 15 14 13

    It can be verified that the sum of the numbers on the diagonals is 101.

    What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral
    formed in the same way?

    
    NOTES

    
    REFERENCES
    
    
    PERFORMANCE
    time <function test_case at 0x7f545b6b8f50>: 0.000334 s
    time <function solution at 0x7f545b6bb0c8>: 9.232575 s
    
"""
#
# Import
#
import time
import random


#
# Globals / Constants
#
LEFT    = (1, 0)
DOWN    = (0, -1)
RIGHT   = (-1, 0)
UP      = (0, 1)

def timeit(f):
    def timer():
        t0 = time.time()
        returned = f()
        print "time %s: %.6f s" % (f, time.time() - t0)
        return returned
    return timer

def assert_match(value, expected, message=""):
    f = "value %s != expected %s"
    f = message != '' and f + " (%s)" or f + "%s"
    assert value == expected, f % (value, expected, message)


#
# Test Case / Solution
#
@timeit    
def test_case():    
    spiral = Spiral(5)
    spiral_sum = spiral.sum_diagnols()
    assert_match(spiral[0,0], 1)
    assert_match(spiral[-2,2], 21)
    assert_match(spiral[1,-1], 3)
    assert_match(spiral_sum, 101)
    
    print "test case passed!"

@timeit
def solution():
    spiral = Spiral(1001)
    return spiral.sum_diagnols()

#
# Solution Code
#
class Spiral(dict):
    
    right   = complex(1,0)
    down    = complex(0,-1)
    left    = complex(-1,0)
    up      = complex(0,1)
    
    def __init__(self, size):
        """assume size greater than 1"""
        self.size = size
        self.width = self.size / 2
        self.height = self.size / 2
        self.build()
        
    def build(self):
        """build a spiral as a dict with key represent (x,y) coordinates and
        value an integer with (0,0) at center. A spiral of size 5 would
        have value of 21 at upper left coordinate (-2,2)."""
        self.current_pt = (0,0)
        self.current_value = 0
        self.direction = Spiral.up  # will turn right at next spiral
        self.add_current_cell()
        
        while not self.is_complete():
            self.spiral()
            
    def sum_diagnols(self):
        """start at upper left and gather all points going downward to the
        right, then start at lower and gather all points going up to right"""
        upper_left = (-self.width, self.height)
        lower_right = (self.width, -self.height)
        lower_left = (-self.width, -self.height)
        upper_right = (self.width, self.height)
        
        # left-down diagnol
        diagnol1 = [(x,y) for (x,y) in zip(
            range(upper_left[0], lower_right[0]+1),
            range(upper_left[1], lower_right[1]-1, -1))]
        
        # left-up diagnol
        diagnol2 = [(x,y) for (x,y) in zip(
            range(lower_left[0], upper_right[0]+1),
            range(lower_left[1], upper_right[1]+1))]
        
        return sum([self[pt] for pt in set(diagnol1 + diagnol2)])
            
    def spiral(self):
        if self.can_go_right():
            self.turn_right()
        
        self.move(self.direction)
        self.add_current_cell()
        if self.current_value > self.size**2:
            raise Exception("invalid spiral")
                
    def is_complete(self):
        return not self.can_go_straight() and not self.can_go_right()
        
    def turn_right(self):
        right = self.rotate_right()
        self.direction = right
            
    def add_current_cell(self):
        self.current_value += 1
        self[self.current_pt] = self.current_value
        
    def can_go_straight(self):
        x,y = self.get_point_in_direction(self.direction)
        return self.pt_is_in_grid(x,y) and not self.pt_is_set(x,y)
        
    def can_go_right(self):
        right = self.rotate_right()
        x,y = self.get_point_in_direction(right)
        return self.pt_is_in_grid(x,y) and not self.pt_is_set(x,y)
        
    def rotate_right(self):
        rotation = complex(-1, -1)
        clockwise = self.direction + (self.direction * rotation)
        return clockwise
        
    def pt_is_in_grid(self, x, y):
        return abs(x) <= self.width and abs(y) <= self.height
        
    def pt_is_set(self, x, y):
        return (x,y) in self
        
    def move(self, direction):
        """direction can be a tuple or complex. Sets next point as current
        point"""
        next_pt = self.get_point_in_direction(direction)
        self.current_pt = next_pt
    
    def get_point_in_direction(self, direction):
        x1, y1 = self.current_pt
        x2, y2 = type(direction) == complex and \
            (direction.real, direction.imag) or direction
        return (int(x1 + x2), int(y1 + y2))

#
# Additional Tests
#


#
# Main
#
if __name__ == '__main__':
    test_case()
    print solution()
    